Search Results

Documents authored by Held, Martin

Document
DOI: 10.4230/LIPIcs.ESA.2020.56
An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams

Authors: Martin Held and Stefan de Lorenzo

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We present a simple wavefront-like approach for computing multiplicatively weighted Voronoi diagrams of points and straight-line segments in the Euclidean plane. If the input sites may be assumed to be randomly weighted points then the use of a so-called overlay arrangement [Har-Peled & Raichel, Discrete Comput. Geom. 53:547 - 568, 2015] allows to achieve an expected runtime complexity of 𝒪(n log⁴ n), while still maintaining the simplicity of our approach. We implemented the full algorithm for weighted points as input sites, based on CGAL. The results of an experimental evaluation of our implementation suggest 𝒪(n log² n) as a practical bound on the runtime. Our algorithm can be extended to handle also additive weights in addition to multiplicative weights, and it yields a truly simple 𝒪(n log n) solution for solving the one-dimensional version of this problem.
Cite as

Martin Held and Stefan de Lorenzo. An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{held_et_al:LIPIcs.ESA.2020.56,
  author =	{Held, Martin and de Lorenzo, Stefan},
  title =	{{An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{56:1--56:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.56},
  URN =		{urn:nbn:de:0030-drops-129224},
  doi =		{10.4230/LIPIcs.ESA.2020.56},
  annote =	{Keywords: Voronoi Diagram, multiplicative weight, additive weight, arc expansion, overlay arrangement, implementation, experiments, CGAL, exact arithmetic}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.38
On Implementing Straight Skeletons: Challenges and Experiences

Authors: Günther Eder, Martin Held, and Peter Palfrader

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We present Cgal implementations of two algorithms for computing straight skeletons in the plane, based on exact arithmetic. One code, named Surfer2, can handle multiplicatively weighted planar straight-line graphs (PSLGs) while our second code, Monos, is specifically targeted at monotone polygons. Both codes are available on GitHub. We discuss algorithmic as well as implementational and engineering details of both codes. Furthermore, we present the results of an extensive performance evaluation in which we compared Surfer2 and Monos to the straight-skeleton package included in Cgal. It is not surprising that our special-purpose code Monos outperforms Cgal’s straight-skeleton implementation. But our tests provide ample evidence that also Surfer2 can be expected to be faster and to consume significantly less memory than the Cgal code. And, of course, Surfer2 is more versatile because it can handle multiplicative weights and general PSLGs as input. Thus, Surfer2 currently is the fastest and most general straight-skeleton code available.
Cite as

Günther Eder, Martin Held, and Peter Palfrader. On Implementing Straight Skeletons: Challenges and Experiences. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eder_et_al:LIPIcs.SoCG.2020.38,
  author =	{Eder, G\"{u}nther and Held, Martin and Palfrader, Peter},
  title =	{{On Implementing Straight Skeletons: Challenges and Experiences}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.38},
  URN =		{urn:nbn:de:0030-drops-121964},
  doi =		{10.4230/LIPIcs.SoCG.2020.38},
  annote =	{Keywords: weighted straight skeleton, implementation, algorithm engineering, experiments, Cgal, Core}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.76
Step-By-Step Straight Skeletons (Media Exposition)

Authors: Günther Eder, Martin Held, and Peter Palfrader

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We present two software packages for computing straight skeletons: Monos, our implementation of an algorithm by Biedl et al. (2015), computes the straight skeleton of a monotone input polygon, and Surfer2 implements a generalization of an algorithm by Aichholzer and Aurenhammer (1998) to handle multiplicatively-weighted planar straight-line graphs as input. The graphical user interfaces that ship with our codes support step-by-step computations, where each event can be investigated and studied by the user. This makes them a canonical candidate for educational purposes and detailed event analyses. Both codes are freely available on GitHub.
Cite as

Günther Eder, Martin Held, and Peter Palfrader. Step-By-Step Straight Skeletons (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 76:1-76:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eder_et_al:LIPIcs.SoCG.2020.76,
  author =	{Eder, G\"{u}nther and Held, Martin and Palfrader, Peter},
  title =	{{Step-By-Step Straight Skeletons}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{76:1--76:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.76},
  URN =		{urn:nbn:de:0030-drops-122343},
  doi =		{10.4230/LIPIcs.SoCG.2020.76},
  annote =	{Keywords: weighted straight skeleton, implementation, visualization, graphical user interface, education}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2020.85
Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions (CG Challenge)

Authors: Günther Eder, Martin Held, Stefan de Lorenzo, and Peter Palfrader

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Our work on minimum convex decompositions is based on two key components: (1) different strategies for computing initial decompositions, partly adapted to the characteristics of the input data, and (2) local optimizations for reducing the number of convex faces of a decomposition. We discuss our main heuristics and show how they helped to reduce the face count.
Cite as

Günther Eder, Martin Held, Stefan de Lorenzo, and Peter Palfrader. Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions (CG Challenge). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 85:1-85:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eder_et_al:LIPIcs.SoCG.2020.85,
  author =	{Eder, G\"{u}nther and Held, Martin and de Lorenzo, Stefan and Palfrader, Peter},
  title =	{{Computing Low-Cost Convex Partitions for Planar Point Sets Based on Tailored Decompositions}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{85:1--85:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.85},
  URN =		{urn:nbn:de:0030-drops-122438},
  doi =		{10.4230/LIPIcs.SoCG.2020.85},
  annote =	{Keywords: Computational Geometry, geometric optimization, algorithm engineering, convex decomposition}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact